"""
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

暴力解法： 先算出最大的高度然后一层一层的计算为0的数量，每一层删减数组左右两端为0 的元素，然后统计每层0的个数累加即为结果
O(n) 解法
        先算出整体的面积在用整体的面积减去原来height的元素，剩下的就是雨水的容量
        Find maximum height of bar from the left end upto an index i in the array left_max
        Find maximum height of bar from the right end upto an index i in the array right_max
        Iterate over the height\text{height}height array and update ans:
        Add min(max_left[i],max_right[i])−height[i] to ansansans
"""

class Solution:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if len(height) <= 1:
            return 0
        high = max(height)
        res = 0
        for i in range(1,high+1):
            s = 0
            while height[s] == 0 and s < len(height):
                s += 1
            e = len(height)-1
            while height[e] == 0 and s >= 0:
                e -= 1
            height = height[s:e+1]
            cur = height.count(0)
            res += cur
            for i,x in enumerate(height):
                if x > 0:
                    height[i] -= 1
        return res

    def trap_opt(self, height):
        dp = []
        maxh = 0
        for i in range(len(height)):
            maxh = max(maxh, height[i])
            dp.append(maxh)
        right = 0
        for i, v in reversed(list(enumerate(height))):
            right = max(right, v)
            dp[i] = min(right,dp[i])-v
        return sum(dp)

s = Solution()
s.trap_opt([4,2,3])